COMMENT ⊗   VALID 00010 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	%logic[f86,jmc]		Mathematical logic and artificial intelligence
C00003 00003	\section{Introduction}
C00015 00004	\section{History}
C00020 00005	\section{Applications of Logic to AI Planning}
C00021 00006	\section{Non-monotonic reasoning}
C00022 00007	\section{Unsolved problems}
C00026 00008	\centerline{This draft of logic[f86,jmc] TEXed on \jmcdate\ at \theTime}
C00027 00009	Notes:
C00030 00010	leftovers
C00032 ENDMK
C⊗;
%logic[f86,jmc]		Mathematical logic and artificial intelligence
%-for Daedalus
\input memo.tex[let,jmc]
\title{MATHEMATICAL LOGIC AND ARTIFICIAL INTELLIGENCE}
%
\section{Introduction}
%
	The idea of using mathematical logic as the basis for
artificial intelligence can be said, in a generous interpretation,
to go back to Leibniz.  He proposed to express the facts about
the world in a form of mathematical logic that was yet to be
invented and to settle arguments about facts and policies by
calculation.  Unfortunately, Leibniz did not succeed even in
inventing propositional calculus, which had to wait for Boole
about 150 years later, who in turn didn't invent predicate
calculus.  Leibniz's failure to invent propositional calculus
requires an explanation, because he was the co-inventor with
Newton of the infinitesimal calculus, which is mathematically
far more complex.  The explanation, I think, is that we humans
find understanding mental processes very difficult,
and progress is slow.  This applies to our own time, as well
as to Leibniz's.  It is quite likely that when mental processes
are well understood, the explanation won't seem deep, and the
scientists of that time will have difficulty explaining why
we missed what then will seem obvious.

	One's approach to the study of intelligence
depends on whether one regards it as a branch of biology
or as a branch of computer science.

	Biologically one studies
processes as a biological phenomenon, mainly observable in
humans, and the essence of that study is to determine
how they are carried out in humans.  The criterion for
judging a proposed intellectual mechanism is whether there
is evidence that it is indeed used by humans.
In particular  we must ask what evidence there is
of the extent to which humans use anything like mathematical
logic in deciding what to do.

	The contrasting computer science view is that mental processes are
concerned with deciding what to do as it depends on the structure of the
world, the structure of information available and how more information can
be obtained, and the structure of goals to be achieved.  From this point
of view, artificial intelligence is a problem in computer science, a
mathematical kind of engineering --- the problem of designing algorithms
to achieve goals.

	For example, if only achieving a goal in the common sense world
consisted of minimizing a known linear function in the presence of known
linear constraints, then artificial intelligence would be coextensive with
the theory of linear programming.  In fact the information structure of
the common sense world is quite different from those amenable to classical
mathematical treatment, and entirely new methods have to be developed.  Of
course, what can be observed or even conjectured about the situations in
which human intelligence is successful or about how human intelligence
works is helpful.  Indeed it may be the main way of inventing AI
mechanisms.  However, the criterion for AI success is how well the
mechanisms work in the common sense world,
not how well they correspond to human intelligence.
Of course, if they don't work on problems humans solve, then they can't
be the way humans function.

	This paper takes the computer science view, even omitting
discussion of the strong interaction between the two research programs.

	There are several ways of studying AI in computer science.  For
example, some have conjectured that intelligence can consist of a very
large number of production rules that determine actions as a function of
patterns observed in a database.  In a formal extensional sense, this
follows trivially from the view that AI is possible at all, because any
program can be written in such a form.  The production-system view
acquires controversial content when it further specificies that additions
to knowledge and capability can consist of adding new production rules to
an existing database without rewriting it from scratch.

\section{Logic in AI}

	The logic based approach to AI involves expressing what the
system knows about the world as sentences in some mathematical logical
language, involves logical inference as the major method of reasoning,
and involves adding new sentences to a database as the major way of
absorbing new knowledge.

	(McCarthy 1960) proposed the following.

\begingroup\narrower\narrower
% COMMON.TEX[E80,JMC]	TeX version Programs with Common Sense
The {\it advice taker} is a proposed program for solving problems by manipulating
sentences in formal languages.  The main difference between it and other programs
or proposed programs for manipulating formal languages (the {\it Logic Theory
Machine} of Newell, Simon and Shaw and the Geometry Program of Gelernter)
is that in the previous programs the formal system was the subject matter
but the heuristics were all embodied in the program.  In this program the
procedures will be described as much as possible in the language itself
and, in particular, the heuristics are all so described.

	The main advantages we expect the {\it advice taker} to have is that
its behavior will be improvable merely by making statements to it,
telling it about its symbolic environment and what is wanted from it.  To
make these statements will require little if any knowledge of the program
or the previous knowledge of the {\it advice taker}.  One will be able to
assume that the {\it advice taker} will have available to it a fairly wide
class of immediate logical consequence of anything it is told and its
previous knowledge.  This property is expected to have much in common with
what makes us describe certain humans as having {\it common sense}.  We
shall therefore say that {\it a program has common sense if it automatically
deduces for itself a sufficiently wide class of immediate consequences of
anything it is told and what it already knows.}
\par\endgroup

	This prospectus was ambitious in 1960 and is still far from realized.
The rest of this paper is concerned with describing what progress has
been made, what the obstacles are, and how the prospectus has been modified
in the light of what has been discovered.

	Before proceeding I want to devote a few sentences to controversy.  AI
itself is controversial, and some people still think machine intelligence
is impossible.  I suppose fewer people have this opinion than
in the 1950s.  They have arguments in principle and arguments from the
slow progress of AI research.  I have discussed the former elsewhere,
(McCarthy 19xx, ).  As for the latter, I merely reiterate that understanding
intelligence is difficult, and unsolved and even unidentified conceptual problems
remain.  It may take 5 years, and it may take 500.  Moreover, most of the
complainers about lack of progress either haven't taken the trouble or
haven't the competence in computer science and mathematical logic
to pay attention to the progress that has been made.

	There is also controversy over the utility of logic in AI,
and its popularity has had ups and downs.  Now seems to be an up,
but some recent arguments against the use of logic are in
(Feigenbaum 19xx), (McDermott 19xx) and (Hewitt 19xx).  A forthcoming
book (Levesque 19xx) contains arguments pro and con including a
discussion by myself and Vladimir Lifschitz.  For lack of time and
space, I will not argue the matter here.  Actually neither the pro
nor the con arguments are in shape to convince adherents of the
other side or even neutrals.  Only the subsequent successes and
failures of the various approaches will do that.
%
\section{History}

	The first computer program for proving theorems in logic
was the 1954 Logic Theorist of Newell, Simon and Shaw.  However,
they were not interested in applying logic to other domains but
rather in making programs that simulated the efforts of a naive
student trying to prove theorems in the pure propositional logic
formalism of Russell and Whitehead.  In (Wang 19xx) it was shown
that such easy theorems could be proved much more quickly by a computer
program that didn't simulate human methods but used a special method
that Wang devised.

	(McCarthy 1960) discussed formalizing the effects going from
one place to another including the preconditions for the success
of the action.  For example, a driving from one place to another
had the preconditions that the driver be at his car and the
origin and destination of the trip be in a region that was ``drivable''.
The particular problem was going to the airport.
In 1964, Fisher Black's Harvard PhD thesis involved a program that
represented the facts of this situation and the general effects of
the relevant actions by logical sentences and deduced a plan for
driving to the airport.

	(McCarthy 1964) proposed a formalism called the {\it situation
calculus} for formalizing such problems, and this formalism was
further developed in (McCarthy and Hayes 1969).

	J. Allan Robinson's 1965 resolution method constituted a
big advance in automatic theorem proving and has led to a long line
of computer programs with many improvements.  In a few domains in
for which people don't have much intuition, such computer programs
were even able to do a few previously unsolved problems.  See (Wos 19xx).

	In 1969 C. Cordell Green used the situation calculus and
the resolution method for some problems in robot planning, e.g.
pushing a block from one room to another.  The program was very
slow, and this led Nils Nilsson and Richard Fikes to propose a
system called STRIPS.  STRIPS reduced the use of a resolution
theorem prover to establishing that the preconditions of an an
action were met in a given situation.  The effects of the action
were computed by a non-logical part of the program that worked
with an {\it add-list} and a {\it delete-list} characteristic
of the action type.  This greatly improved the speed at the cost
of specialization.  In particular, STRIPS does not allow sentences
that compare different situations.

	Restricting the scope in which deduction is used in order
to achieve increased speed and accepting the resulting specialization has been
a theme of much research in AI.  Dissatisfaction with the resulting
narrowly applicable programs has led to more recent efforts to
use the full situation calculus or some other logical formalism
and control the inference by other means.  The idea of (McCarthy 1960)
quoted above of using sentences in the language itself to control the
inference has never been realized, because no-one has figured out
how to express the heuristic information in declarative sentences.
The reader is at liberty to stake his reputation on the proposition
that no-one ever will.
\section{Applications of Logic to AI Planning}
%
	One of the most important areas of application of logic in AI
has been {\it planning}.  The term {\it planning} in AI refers to
determining from the facts available a sequence of actions that
will achieve a goal.  [The planning formalisms used in operations
research may be regarded as a special case wherein the actions
to be taken are predetermined and only their order is to be
determined.]  For planning the key facts are those that describe
the consequences of actions.
\section{Non-monotonic reasoning}
\section{Unsolved problems}

\noindent Elaboration Tolerance

	Physics, mathematics and applied sciences like operations
research all construct mathematical models in similar ways.  A person
decides what phenomena are to be taken into account, and the mathematical
model deals precisely with these phenomena and the specified
relations among these phenomena.  If the model proves inadequate,
it is again up to a person to modify or extend it.  For AI this
won't do in the long run, because if the program is to behave fully
intelligently, it must decide what phenomena to take into account.
Consequently, the formalism must be open ended, and must tolerate
subsequent elaboration still staying within the formalism.  From
the technical logical point of view, this raises problems with
the notions of interpretation and model, which seem to require that
the domain be specified.  Some people, e.g. Hewitt (19xx), have
claimed that this shows that mathematical logic can't be used
in AI when ``open worlds'' are required.

	It isn't yet clear how the problem will be finally solved,
but one approach is to work in a domain of formalized concepts and
in a language rich in functions that build new concepts from old
ones.
%x

\noindent The Common Sense Database

	The languages and sets of axioms so far used in AI have
dealt with example situations.  This is true both of the research
systems and the applied systems.  There has been no attempt to
claim that the particular language used, e.g. the language of
moving objects of section yy, covers even the main uses of the concepts
that we shall want programs to make.  One present project is to
determine a language for a general common sense database that
will contain the facts about various phenomena in a way that
can be used by any program needing them.

\noindent Declarative Control of Inference

	The extract from (McCarthy 1960) promises that control
of the facts taken into account and the order of inference
will be specifiable by telling the system facts about what
possibilities are worth examining.  Even at that time it was
apparent that uncontrolled deduction from the domain facts would
lead to combinatorial explosion.  Such flexible control of
reasoning still remains to be achieved.
\centerline{This draft of logic[f86,jmc] TEXed on \jmcdate\ at \theTime}
\centerline{Copyright \copyright\ by John McCarthy \number\year}
\vfill\eject\end
Notes:
sentences as propensities to behave

a different view of some philosophical issues comes from taking AI
seriously - the design stance.

let's be arrogant, AI also helps psychology, rehabilitates old
ideas like even will-power, it also may help the social sciences
in general by offering improved treatments of reasoning with
insufficient information an computation power.

generality problem

blocks world and general motion axiom

context problem

elaboration tolerance

It is not my objective in this article to engage in controversy,
but I should certainly mention that controversy exists.  Perhaps
when I see the other articles, I'll regret this decision.

use of logical formalism to express facts
	ad hoc programs for reasoning
	answering questions
	achieving goals

At present our view of achieving this goal is obscured by our
lack of understanding of a number of inadequately formulated
problems.


Why should we expect progress if there are all these problems?
Usually in science this is a dumb question, and I really think
it's just as dumb here.  However, the jackals and wolves of the anti-science
movement so prominent in Cambridge and Berkeley
tend to attack where they think there are weaknesses,
and a number of scientists, including at least one distinguished physicist,
are inclined to throw babies out of the sleigh to distract the wolves.
Therefore, I'll answer the question in some detail.

logic programming

resolution

non-monotonic reasoning

elaboration tolerance and the common sense database

outline

1. Introduction
	Why logic
leftovers
	Using logic for representing a database of facts about the
common sense world requires methods quite different from those
used in formalizing mathematics or those used in physical sciences
or in operations research.  In the sciences, one first decides
what phenomena one is going to take into account.  Then one decides
on what objects are in the domain of reasoning and what their
relations are.  This defines the mathematical model to be used.
The process of determining the mathematical model is informal.
Only after the model has been decided are the formal methods
applicable.  If we adopt this model in AI, we are beaten before
we start.  Intelligent behavior includes the determination of
what phenomena are to be taken into account, and our robots and other
intelligent computer programs must do this too.